package com.itheima.algorithm.datastructure;

/**
 * 判断链表是否有环
 * @Author: zhangshao
 * @Since: 2024/5/7 17:19
 */
public class Leetcode142 {
	public static ListNode detectCycle(ListNode head){
		// 兔
		ListNode h = head;
		// 龟
		ListNode t = head;

		while(h!=null && h.next!=null){
			// 还没走到终点

			t = t.next;
			h = h.next.next;
			if(h == t){
				//进入第二阶段
				t = head;
				while (true){
					// 如果本身是个环, 刚开始即相遇
					if(h == t){
						return t;
					}
					t = t.next;
					h = h.next;
				}

			}
		}
		return null;
	}

	public static void main(String[] args) {

		ListNode n10 = new ListNode(10,null);
		ListNode n9 = new ListNode(9,n10);
		ListNode n8 = new ListNode(8,n9);
		ListNode n7 = new ListNode(7,n8);
		ListNode n6 = new ListNode(6,n7);
		ListNode n5 = new ListNode(5,n6);
		ListNode n4 = new ListNode(4,n5);
		ListNode n3 = new ListNode(3,n4);
		ListNode n2 = new ListNode(2,n3);
		ListNode n1 = new ListNode(1,n2);

		n10.next = n8;

		System.out.println(detectCycle(n1).value);

	}
}
